package com.zhupf.dynamic;

import java.text.SimpleDateFormat;
import java.time.*;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
import java.util.List;

/**
 * @author zhupf
 * @date 2024年04月12日 14:55
 * @Description
 *  416. 分割等和子集
 *
 *  给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 示例 1：
 *
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 * 示例 2：
 *
 * 输入：nums = [1,2,3,5]
 * 输出：false
 * 解释：数组不能分割成两个元素和相等的子集。
 *
 */
public class CanPartition {

    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%2 !=0 || nums.length == 1){
            return false;
        }
        int target = sum/2;

        int[][] dp = new int[nums.length][target+1];
        for (int i = 0; i < nums.length; i++) {
            if(nums[0] > target){
                return false;
            }
            dp[i][0] = 1;
        }

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            for(int j = 1; j<= target;j++){
                if(j>=num){
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-num];
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }

        }
        return dp[nums.length-1][target]==1;
    }

    public static boolean canPartition2(int[] nums) {
        int sum = 0;
        int max = 0;
        for (int num : nums) {
            sum+=num;
            max = Math.max(max,num);
        }
        if(sum%2 !=0 || nums.length == 1){
            return false;
        }
        int target = sum/2;
        int[][] dp = new int[nums.length][target+1];
        for (int num : nums) {
            if(num>max){
                return false;
            }
        }
        return process(target,nums,0,dp);
    }

    private static boolean process(int target,int[] nums, int i,int[][] dp){
        if(target==0){
            return true;
        }
        if(target<0 || i>= nums.length){
            return false;
        }
        if(dp[i][target] != 0){
            return dp[i][target] == 1;
        }
        boolean res = process(target - nums[i], nums, i + 1,dp) ||  process(target , nums, i + 1,dp);
        dp[i][target] = res?1:-1;
        return  res;
    }

}
